public class avlTree {

    static class treeNode{
        int val;//节点存储的值
        treeNode left;//左孩子节点
        treeNode right;//右孩子节点
        treeNode parent;//父亲节点
        int bf;//平衡因子
        //构造方法
        public treeNode(int val) {
            this.val = val;
        }
    }

    public treeNode root;

    public boolean insert(int val){
        treeNode node=new treeNode(val);
        if(root==null){
            root=node;
        }
        treeNode parent=null;
        treeNode cur=root;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){
                return false;
            }else {
                parent=cur;
                cur=cur.left;
            }
        }
        if(parent.val>val){
            parent.left=node;
            node.parent=parent;
        }else {
            parent.right=node;
            node.parent=parent;
        }
        cur=node;

        while(parent!=null){
            if(cur==parent.left){
                parent.bf++;
            }else {
                parent.bf--;
            }

            if(parent.bf==0){
                return true;
            }else if(parent.bf==-1||parent.bf==1){
                cur=parent;
                parent=parent.parent;
            }else {
                if(parent.bf==2){
                    if(cur.bf==1){//右旋
revolveLL(parent);
                    }else {//左右双旋
revolveLR(parent);
                    }
                }else {
                    if(cur.bf==1){//右左双旋
revolveRL(parent);
                    }else {//左旋
revolveRR(parent);
                    }
                }
                break;
            }
        }
return true;
    }

    private void revolveLL(treeNode parent){
treeNode subL=parent.left;//旋转中心
treeNode subLR=subL.right;//冲突的右孩

        //处理右孩为空的情况
if(subLR!=null){
    subLR.parent=parent;
}
parent.left=subLR;//右孩和旋转点建立联系
//处理旋转点是否是根节点的情况
        if(parent==root){
            root=subL;
            subL.right=parent;
        }else{
           treeNode pParent=parent.parent;
           if(parent==pParent.left){
               pParent.left=subL;
           }else {
               pParent.right=subL;
           }
           subL.parent=pParent;
        }
        //旋转中心和旋转点建立联系
        parent.parent=subL;
        subL.right=parent;
        //修改平衡因子
subL.bf=parent.bf=0;
    }

    private void revolveRR(treeNode parent){
treeNode subR=parent.right;//旋转中心
treeNode subRL=subR.left;//冲突的左孩
        //冲突的左孩是否为空
        if(subRL!=null){
            subRL.parent=parent;
        }
        parent.right=subRL;
        //父亲节点是否为根节点
        if(parent==root){
            subR.parent=null;
            root=subR;
        }else {
            treeNode pParent=parent.parent;
            if(parent==pParent.left){
                pParent.left=subR;
            }else {
                pParent.right=subR;
            }
            subR.parent=pParent;
        }
        //处理旋转点和旋转中心的关系
        parent.parent=subR;
        subR.left=parent;
        //修改平衡因子
        parent.bf=0;
        subR.bf=0;
    }
    private void revolveLR(treeNode parent){
        treeNode subL=parent.left;
        treeNode subLR=subL.right;
        int bf=subLR.bf;
revolveRR(parent.left);//先左旋父亲节点的左孩子节点
revolveLL(parent);//再右旋父亲节点
        if(bf==1){
            parent.bf=-1;
            subL.bf=0;
            subLR.bf=0;
        }else if(bf==-1){
            parent.bf=0;
            subL.bf=1;
            subLR.bf=0;
        }
    }
    private void revolveRL(treeNode parent){
treeNode subR=parent.right;
treeNode subRL=subR.left;
int bf=subRL.bf;
revolveLL(parent.right);
revolveRR(parent);
if(bf==1){
            parent.bf=0;
            subRL.bf=0;
            subR.bf=-1;
}else if(bf==-1){
    parent.bf=1;
    subRL.bf=0;
    subR.bf=0;
}
    }



    public boolean isBalanced(treeNode root){
        if(root==null){
            return true;
        }
        int leftH=height(root.left);
        int rightH=height(root.right);
        //判断左右树高差的绝对值是否小于等于1，并且递归判断每一个节点是否满足要求
        return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }

//获取左右树高
    private int height(treeNode node){
        if(node==null){
            return 0;
        }
        int leftH=height(node.left);
        int rightH=height(node.right);
        return Math.max(leftH,rightH)+1;
    }

    public void inOrder(treeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    


}
